1. Field of the Invention
The present invention relates to synchronization amongst execution sequences in computer programs and, in some applications thereof, to techniques for facilitating garbage collection in multi-threaded software environments.
2. Description of the Related Art
Traditionally, most programming languages have placed responsibility for dynamic allocation and deallocation of memory on the programmer. For example, in the C programming language, memory is allocated from the heap by the malloc procedure (or its variants). Given a pointer variable, p, execution of machine instructions corresponding to the statement p=malloc (sizeof (SomeStruct)) causes pointer variable p to point to newly allocated storage for a memory object of size necessary for representing a SomeStruct data structure. After use, the memory object identified by pointer variable p can be deallocated, or freed, by calling free (p). Pascal and C++ languages provide analogous facilities for explicit allocation and deallocation of memory.
Unfortunately, dynamically allocated storage becomes unreachable when no chain of references (or pointers) can be traced from a “root set” of references (or pointers) to the storage. Memory objects that are no longer reachable, but have not been freed, are called garbage. Similarly, storage associated with a memory object can be deallocated while still referenced. In this case, a dangling reference has been created. In general, dynamic memory can be hard to manage correctly. In most programming languages, heap allocation is required for data structures that survive the procedure that created them. If these data structures are passed to further procedures or functions, it may be difficult or impossible for the programmer or compiler to determine the point at which it is safe to deallocate them.
Because of this difficulty, garbage collection, i.e., automatic reclamation of heap-allocated storage after its last use by a program, can be an attractive alternative model of dynamic memory management. Garbage collection is particularly attractive for languages such as the Java™ language (Java and all Java-based marks and logos are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries), Prolog, Lisp, Smalltalk, Scheme, Eiffel, Dylan, ML, Haskell, Miranda, etc. See generally, Jones & Lins, Garbage Collection: Algorithms for Automatic Dynamic Memory Management, pp. 1–41, Wiley (1996) for a discussion of garbage collection and of various classical algorithms for performing garbage collection.
In general, garbage collection methods can be described with reference to a garbage collection strategy implemented by a “collector” and its interaction or coordination with a useful computation—a “mutator”—that changes the state of heap-allocated storage. Many collector implementations, including some mark-sweep and copying collector implementations, are based on a stop-start approach, i.e., they involve suspending the mutator, collecting garbage, and resuming execution of the mutator after garbage collection. In such implementations, garbage collection is performed when the “root set” of pointers to dynamically allocated memory locations referenceable by the mutator is available to the garbage collector. A mutator in this state is called “consistent,” and one that is not is “inconsistent.”
Typically, a compiler for a garbage-collected language supports the collector by generating code that allocates objects, by describing storage locations that make up the root set, and by describing the layout of objects allocated from the heap. For efficiency, compilers typically generate code that uses registers and/or stack locations provided by a target processor architecture. As a result, execution of compiled code puts pointers in such registers or stack locations. Unfortunately, a mutator running such code is generally inconsistent, because the exact set of registers and/or stack locations containing pointers can change with every instruction. The overhead of exactly maintaining a root set description at each instruction tends to defeat the purpose of using registers and stack locations in the first place. Compilers therefore identify safe points in the code, places in the code where the compiler emits information describing which registers and stack locations contain pointers. When a mutator is suspended at a safe point it is consistent and hence garbage collection can proceed. See generally, Appel, Modern Compiler Implementation in C: Basic Techniques, pp. 291–297, Cambridge University Press (1998) for a description of compiler support for garbage collection.
Accordingly, a mechanism is desired by which a processor executing mutator code may suspend execution at a safe point defined therein to facilitate garbage collection. A desirable mechanism is computationally efficient and imposes minimal overhead on the mutator computation. Furthermore, it is desirable for the mechanism to operate in the context of multi-threaded mutator computation and to limit the delay between a request to start garbage collection and suspension of all threads of the mutator computation.